package leetcode.f1t100;

/**
 * 矩阵从左到右升序, 下一场第一个值比上一行末尾大, 在矩阵中寻找目标值
 * https://leetcode.com/problems/search-a-2d-matrix/
 *
 * @Author lichongxiao
 * @Date 2022/11/24 9:56
 */
public class Q74_SearchA2DMatrix {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] >= target) {
                return matrix[0][j] == target;
            }
        }
        for (int i = 0; i < m; i++) {
            if (matrix[i][n - 1] == target) {
                return true;
            } else if (matrix[i][n - 1] > target) {
                for (int j = n - 2; j >= 0; j--) {
                    if (matrix[i][j] <= target) {
                        return matrix[i][j] == target;
                    }
                }
                break;
            }
        }
        return false;
    }
}
